//https://leetcode.cn/problems/escape-the-spreading-fire/?envType=daily-question&envId=2023-11-09


int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
class Solution {
public:
    int maximumMinutes(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        vector<vector<int>> f(n, vector<int>(m, INT_MAX));

        queue<pair<int, int>> q;
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < m; ++j) if(grid[i][j] == 1) q.emplace(i,j), f[i][j] = 0;
        while(!q.empty()) {
            auto [x, y] = q.front(); q.pop();
            for(int i = 0; i < 4; ++i) {
                int nx = x+dx[i], ny = y+dy[i];
                if(nx<n && nx>=0 && ny<m && ny>=0 && !grid[nx][ny] && f[nx][ny] == INT_MAX){
                    q.emplace(nx, ny);
                    f[nx][ny] = f[x][y]+1;
                } 
            }
        }

        auto check = [&](int t) {
            vector<vector<int>> d(n, vector<int>(m, INT_MAX));
            queue<pair<int, int>> q;
            q.emplace(0, 0);
            d[0][0] = t;
            while(!q.empty()){
                auto [x, y] = q.front(); q.pop();
                for(int i = 0; i < 4; ++i) {
                    int nx = x+dx[i], ny = y+dy[i];
                    if(nx<n && nx>=0 && ny<m && ny>=0 && d[nx][ny]==INT_MAX && !grid[nx][ny]){
                        d[nx][ny] = d[x][y]+1;
                        if(nx==n-1 && ny==m-1) return d[nx][ny]<=f[nx][ny];
                        else if(d[nx][ny] < f[nx][ny]) q.emplace(nx, ny);
                    } 
                }
            }
            return false;
        };
        int x = 0, y = m*n;
        while(x < y) {
            int m = x+y >> 1;
            if(check(m)) x = m+1;
            else y = m;
        }
        return x == m*n ? 1e9 : x-1;
    }
};